package leetcode.offer;

import leetcode.base.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * ClassName: Offer68I_LowestCommonAncestor
 * Description:
 * date: 2021-11-14 21:47
 *
 * @author liyifan
 */
public class Offer68I_LowestCommonAncestor {

    ArrayList<TreeNode> pPath = new ArrayList<>();

    ArrayList<TreeNode> qPath = new ArrayList<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        findPath(root, p, 0);
        findPath(root, q, 1);
        System.out.println("pPath");
        for (int i = 0;i < pPath.size();i++) {
            System.out.println(pPath.get(i));
        }
        System.out.println("qPath");
        for (int i = 0;i < qPath.size();i++) {
            System.out.println(qPath.get(i));
        }
        for (int i = pPath.size() - 1; i > 0; i--) {
            if (qPath.contains(pPath.get(i))){
                return qPath.get(i);
            }
        }
        return null;
    }

    public void findPath(TreeNode root, TreeNode temp, int flag){
        if (temp.val == root.val) {
            if (flag == 0) {
                pPath.add(temp);
            } else {
                qPath.add(temp);
            }
            return;
        } else if (temp.val < root.val) {
            if (flag == 0) {
                pPath.add(root.left);
            } else {
                qPath.add(root.left);
            }
            findPath(root.left, temp, flag);
        } else {
            if (flag == 0) {
                pPath.add(root.right);
            } else {
                qPath.add(root.right);
            }
            findPath(root.right, temp, flag);
        }
    }

}
